/**
 * 滑动窗口最大值
 * 使用单调递减队列（双端队列）来高效求解
 * 时间复杂度: O(n)，每个元素最多入队和出队一次
 * 空间复杂度: O(k)，队列最多存储 k 个元素
 * 
 * @param nums 输入数组
 * @param k 窗口大小
 * @returns 每个滑动窗口的最大值数组
 */
function maxSlidingWindow(nums: number[], k: number): number[] {
    // 使用双端队列存储数组索引，队列中索引对应的值保持单调递减
    // 队首元素始终是当前窗口最大值的索引
    const q: number[] = [];
    
    // 初始化：构建第一个窗口 [0, k-1] 的单调队列
    for (let i = 0; i < k; ++i) {
        // 维护单调递减性：如果当前元素大于等于队尾元素对应的值，则移除队尾
        // 这样可以保证队列中索引对应的值是单调递减的
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        // 将当前索引加入队列
        q.push(i);
    }
    
    // 第一个窗口的最大值
    let ans: number[] = [nums[q[0]]];
    
    // 滑动窗口：从索引 k 开始，每次向右移动一位
    for (let j = k; j < nums.length; ++j) {
        // 维护单调递减性：新加入的元素如果大于等于队尾元素，则移除队尾
        // 这样可以保证队列中始终存储的是可能成为最大值的元素
        while (q.length > 0 && nums[j] >= nums[q[q.length - 1]]) {
            q.pop();
        }
        // 将新元素的索引加入队列
        q.push(j);
        
        // 移除窗口外的元素：如果队首元素的索引已经不在当前窗口内（索引 <= j-k），则移除
        // 当前窗口范围是 [j-k+1, j]，所以索引 <= j-k 的元素需要移除
        while (q[0] <= j - k) {
            q.shift();
        }
        
        // 队首元素就是当前窗口最大值的索引
        ans.push(nums[q[0]]);
    }

    return ans;
}
